/*
数据结构：单链表
author:lady_killer9
博客：https://blog.csdn.net/lady_killer9
增：尾插、头插、指定元素后插
删：头删、尾删、指定元素后删
头结点、尾节点：返回头结点、尾节点
长度：链表长度
查找：查找第一个val
// 遍历：
//	for e := lst.Front(); e != nil; e = e.Next() {
//		// do something with e.Val
//	}
*/

package singlelist

import "fmt"

//---------单链表节点-----------
type ListNode struct {
    Val interface{}
    next *ListNode
    lst *SingleList
}

//----------获得下一个元素----------
//用于遍历
func (node *ListNode)Next() *ListNode {
	return node.next
}

//---------带头结点单链表-------
type SingleList struct {
	head *ListNode
	len int
}

//---------初始化-------------
func (lst *SingleList)Init(){
	lst.head = new(ListNode)
	lst.head.lst = lst
	lst.len = 0
}

//----------创建单链表-----------
//返回初始化后的头结点单链表
func New() *SingleList {
	lst := new(SingleList)
	lst.Init()
	return lst
}

//----------清空---------------
func (lst *SingleList)Clear(){
	lst.Init()
}

//-----------返回第一个结点--------
//头结点的下一个，可能为nil
func (lst *SingleList)Front() *ListNode {
	return lst.head.Next()
}

//------------返回尾结点---------
//最后一个，可能为nil
func (lst *SingleList)Back() *ListNode {
	if lst.len == 0{
		return nil
	}
	cur := lst.head.Next()
	for{
		if cur.Next() == nil{
			return cur
		}
		cur = cur.Next()
	}
}

//-----------插入---------
//at后插入e，返回e，仅在此函数增加长度
func (lst *SingleList)insert(e, at *ListNode) *ListNode{
	lst.len++
	e.next = at.next
	at.next = e
	e.lst = lst
	return e
}

//------------指定元素后插--------
//mark后插入val
//插入成功返回插入元素，否则返回nil
func (lst *SingleList)InsertAfter(val interface{}, mark *ListNode) *ListNode {
	if mark == nil{
		return nil
	}
	if mark.lst == lst{
		return lst.insert(&ListNode{Val:val},mark)
	}
	return nil
}

//--------------尾插--------------
//调用InsertAfter和Back进行val的尾插
//成功返回插入的元素
func (lst *SingleList)PushBack(val interface{}) *ListNode{
	end := lst.Back()
	if end == nil{
		return lst.InsertAfter(val,lst.head)
	}else {
		return lst.InsertAfter(val,end)
	}
}

//--------------头插------------
//调用InsertAfter进行val的头插
//成功返回插入的元素，否则返回nil
func (lst *SingleList)PushFront(val interface{}) *ListNode {
	return lst.InsertAfter(val,lst.head)
}

//-------------------------删除-----------------------
//仅在此函数减少长度，返回删除的元素或nil
func (lst *SingleList)remove(e *ListNode) *ListNode{
	nextOne := e.next
	if nextOne == nil{
		return nil
	}
	lst.len--
	e.next = e.next.next
	nextOne.lst = nil
	return nextOne
}

//-------指定元素后删---------
func (lst *SingleList)RemoveAfter(e *ListNode) *ListNode{
	if e == nil{
		return nil
	}
	if e.lst == lst{
		return lst.remove(e)
	}
	return nil
}

//--------------前删---------------
func (lst *SingleList)RemoveFront() *ListNode {
	return lst.remove(lst.head)
}

//------------显示单链表----------
//head:头结点
func (lst *SingleList)ShowList()  {
	for cur := lst.Front();cur!=nil;cur = cur.Next(){
		fmt.Print(cur.Val," ")
		cur = cur.Next()
	}
	fmt.Println()
}

//------------单链表长度-----------
func (lst *SingleList)Len() int {
	return lst.len
}
